﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
//216.组合总和III


class Sol216
{
    IList<IList<int>> res;

    public IList<IList<int>> CombinationSum3(int k, int n)
    {
        {
            res = new List<IList<int>>();
            List<int> newList = new List<int>();
            DFS(n,k, 1, newList);

            return res;

        }
    }
    
    void DFS2(int target, int times, int startIndex, IList<int> list)//经典递归,
    {//递归终止条件
        if (list.Count == times)
        {//个数满足条件
         //看一下总和
            int sum = 0;
            for (int i = 0; i < list.Count; i++)
            {
                sum += list[i];
            }
            if (sum == target) { res.Add(list); }


            return;
        }



        for (int i = startIndex; i <= 9; i++)
        {

            List<int> newList = new List<int>(list);
            newList.Add(i);//加入队列

            DFS(target, times, i + 1, newList);
        }





    }
    void DFS(int target, int times, int startIndex, IList<int> list)//经典递归,剪枝
    {
        Console.WriteLine("找到一个startIndex" + startIndex);
        Console.WriteLine("找到一个"+ target);
       

        //递归终止条件
        if (list.Count == times)
        {//个数满足条件
        
            if (0== target) {
                
                res.Add(list); }


            return;
        }

        if (startIndex > target)
        {
            return;
        }//剪枝

        for (int i = startIndex; i <= 9; i++)//剪枝，target小于9，就不要继续了
        {

            List<int> newList = new List<int>(list);
            newList.Add(i);//加入队列


            DFS(target-i, times, i + 1, newList);
        }





    }
}
class Program216
{



    static void Main216(string[] args)
    {
        Sol216 s = new();
        int target = 9, times = 3;
        IList<IList<int>> myres = s.CombinationSum3( times, target);
        for (int i = 0; i < myres.Count; i++)
        {
            for (int j = 0; j < myres[i].Count; j++)
            {

                Console.Write(myres[i][j] + "   ");
            }

            Console.WriteLine();
        }


    }

}

